#include <stdio.h>
#include  <windows.h>

int maxSubArray(int nums[], int numsSize){
	return (maxSubSum(nums, 0, numsSize));
}

int maxSubSum(int *nums, int left, int right){
	int mid, sum = 0, left_sum = 0, right_sum = 0, allmax = 0;
	if (left == right){
		return nums[left];
	}
	mid = (left + right) / 2;
	left_sum = maxSubSum(nums, left, mid);
	right_sum = maxSubSum(nums, mid + 1, right);
	for (int i = mid; i >= left; i--){
		sum += nums[i];
		if (allmax < sum){
			allmax = sum;
		}
	}
	sum = allmax;
	for (int i = mid + 1; i <= right; i++){
		sum += nums[i];
		if (allmax < sum){
			allmax = sum;
		}
	}
	if (allmax < left_sum && right_sum < left_sum){
		return left_sum;
	}
	if (allmax < right_sum){
		return right_sum;
	}
	return allmax;
}

int main()
{
	int arr[] = { -2,-1 };
	int sz = sizeof(arr) / sizeof(arr[0]) - 1;
	printf("%d\n", maxSubArray(arr, sz));
	system("pause");
}

